package SingleMachineArrangeImpl;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

//2.3 总延误问题
// 无条件限制，不可中断
// 这个代码可能写得不对
public class EDDpd extends SingleMachineArrange{

    int mintd = Integer.MAX_VALUE;
    List<Artifact> optSort;

    private int findMaxPj(List<Artifact> artifacts){
        return findMaxPj(artifacts,0,artifacts.size());
    }

    private int getTotalDelay(List<Artifact> artifacts,int low,int high){
        int td = 0;
        int t = 0;
        for (int i = low; i < high; i++) {
            t += artifacts.get(i).process;
            td += Math.max(t-artifacts.get(i).due,0);
        }
        return td;
    }

    private int findMaxPj(List<Artifact> artifacts,int low,int high){
        int imaxp = -1;
        int maxp = Integer.MIN_VALUE;
        for (int i = low; i < high; i++) {
            Artifact artifact = artifacts.get(i);
            if(artifact.process > maxp){
                maxp = artifact.process;
                imaxp = i;
            }
        }
        return imaxp;
    }

    //只对指定范围内的工件进行排序，得到最优序列
    private void getOptSort(List<Artifact> artifacts, int low, int high){
        if(low>=high) {
            int totalDelay = getTotalDelay(artifacts, 0, artifacts.size());
            if(totalDelay < mintd){
                mintd = totalDelay;
                optSort = new ArrayList<>(artifacts);
                System.out.println("当前取得更优排序：" + artifacts);
                System.out.println("总延误：" + totalDelay);
            }
            return;
        }
        //maxPj 一定在low与high之间
        int maxPj = findMaxPj(artifacts, low, high);
        for (int i = maxPj; i < high; i++) {
            //交换 a1 a2
            Artifact a1 = artifacts.get(i);
            Artifact a2 = artifacts.get(maxPj);
            artifacts.set(maxPj,a1);
            artifacts.set(i,a2);
            //尝试在两端取得最优排序
            getOptSort(artifacts,low,i);
            getOptSort(artifacts,i+1,high);
            //还原 a1 a2
            artifacts.set(maxPj,a2);
            artifacts.set(i,a1);
        }
    }

    @Override
    public void solve() {
        if(process==null||due==null){
            process = new int[]{79, 121, 147, 83, 130};
            due = new int[]{260, 266, 269, 336, 337};
        }
        List<Artifact> artifacts = new ArrayList<>();
        for (int i = 0; i < process.length; i++) {
            Artifact a = new Artifact();
            a.process = process[i];a.due = due[i];
            artifacts.add(a);
        }
        //将所有工件按照时间排序
        artifacts.sort(Comparator.comparingInt(artifact -> artifact.due));
        mintd = Integer.MAX_VALUE;
        getOptSort(artifacts,0,artifacts.size());
    }
}
